//
//  Simple.swift
//  AlgorithmProgram
//
//  Created by Bruce Jiang on 2020/4/11.
//  Copyright © 2020 Bruce Jiang. All rights reserved.
//

import Foundation
func reverse(x: Int) -> Int {
       if x > Int32.max || x < Int32.min { return 0 }
       var x1: Int = x
       var ret: Int = 0
       let neg: Int = (x < 0) ? -1 : 1
       x1 *= neg
       while x1 > 0 {
           var n: Int = ret
           n *= 10
           n += x1 % 10
           x1 /= 10
           if n > Int32.max || n < Int32.min { return 0 }
           ret = n
       }
       return ret * neg
   }
   
   func stringReverse(n: Int) -> Bool {
       let s: String = "\(n)"
       let rs = String.init(s.reversed())
       print(rs)
       return s == rs
   }
   
   func isPalindrome(_ x: Int) -> Bool {
       // 排除负数以及可以整除10的数但是x==0应该return true
       if x < 0 || x % 10 == 0 && x != 0 {
           return false
       }
       var X = x
       var reverse = 0
       // 只反转X的一半，如何判断是一半？
       // 当已反转reverse > 变化后的X，则此时已反转X的一半或多一位
       // 譬如X=12321，当reverse==123，X==12，此时已反转X的一半多一位
       // 譬如x=1221，当reverse==12，X==12，此时已反转X的一半
       while X > reverse {
           reverse = reverse * 10 + X % 10
           X /= 10
           print("reverse : \(reverse)")
           print("X: \(X)")
       }
       return X == reverse || X == reverse / 10
   }
   
   func romanToInt(_ s: String) -> Int {
       let dict: [Character : Int] = ["I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000]
       var lastNum = 0
       var result = 0
       for c in s {
           let num = dict[c]!
           result += num
           print(result)
           if num > lastNum {
               result -= 2*lastNum
               print("❌special --- \(result)")
           }
           lastNum = num
       }
       return result
   }
   
   func longestCommonPrefix(_ strs: [String]) -> String {
       if strs.count == 0 { return "" }
       if strs.count == 1 { return strs[0] }
       var retStr: String = ""
       let sortedStrs: [String] = strs.sorted { (s1, s2) -> Bool in
           return s1.count < s2.count
       }
       if let _shortestStr = sortedStrs.first, !_shortestStr.isEmpty {
           retStr = _shortestStr
           let shortestCount: Int = _shortestStr.count
           for i in (1 ... shortestCount).reversed() {
               for j in 1 ..< sortedStrs.count {
                   let currentStr = sortedStrs[j]
                   let currentSubStr = currentStr.prefix(i)
                   let string_currentSubStr = String.init(currentSubStr)
                   if retStr != string_currentSubStr {
                       if i - 1 <= 0 {
                           return ""
                       }
                       retStr = String.init(retStr.prefix(i - 1))
                       break
                   }else {
                       if j == strs.count - 1 {
                           return retStr
                       }
                   }
               }
           }
       }
       
       return retStr
   }
   
   func isValid(_ s: String) -> Bool {
       if s.isEmpty || s.count / 2 == 0 { return false }
       let dic: [Character:Character] = ["{": "}","[": "]", "(": ")"]
       var lefts: [Character] = []
       for c in s {
           if let _ = dic[c] {
               lefts.append(c)
           }else {
               if let _last = lefts.last,
               let _right = dic[_last],
               _right == c {
                   lefts.removeLast()
               }else {
                   return false
               }
           }
       }
       return lefts.count == 0
   }
